#include "basicSort.h"
#include "util.h"
#include "sortCommon.h"
/*
 * Bubble sort-Version1 : Ascending style  
 *
 */

void bubbleSort(int array[], int n)
{
	if (n <= 1 || array == nullptr)
		return;
	
	for (int i = 0; i < n; i++)
	{
		int swap = 0;
		int tmp = 0;
        /* Ascending */
		for (int j = 0; j < n-1-i; j++)
		{
			if (array[j] > array[j + 1])
			{
				tmp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = tmp;
				swap = 1;
			}
		}
		if (!swap)
		{
			break;
		}
	}
}

/*
 * Bubble sort-Version2 : Descending style  
 *
 */

void bubbleSort1(int a[], int n)
{
    if(a == nullptr || n <= 1)
    {
        return;
    }

    int i, j, v;
    
    for(i = 0; i < n; i++)
    {

        bool exit_advance = true;
        for(j = 0; j < n - 1 - i; j++)
        {
            /* Descending */
            if(a[j] < a[j+1])
            {
                v = a[j+1];
                a[j+1] = a[j];
                a[j] = v;
                exit_advance = false;
            }
        }
        if(exit_advance)
            break;

    }

}
/*
 * Insertion sort-Version1 : Ascending style 
 */
void insertSort(int array[], int n)
{
	if (array == nullptr || n <= 1)
		return;

	/* Divide @array into two sector : sorted and unsorted */
    /* sorted sectore starts with index 0(i), unsorted with index 1(i+1) */
    /* get a ele from unsorted and insert it into sorted */

	int i, v, j;
	/* Ascending  */
	for (i = 1; i < n; i++)
	{
		v = array[i];//get a value from unsorted sector 
        /* compare @v and the last ele of the sorted sector */
        /* interate the sorted sector in Descended sort */
		j = i - 1;//emphasize j starts with i - 1
		for (; j >= 0; j--)
		{
			if (v < array[j])
			{
                /* "move ele front to back one by one " */
				array[j + 1] = array[j];
			}
			else
			{
				break;
			}
		}
		/* j-- done when come here */
        /* In loop above, j-- done, and do judgement "j>=0" */
        /* so index is j+1 */
		array[j+1] = v;

	}

}

/*
 * Insertion sort-Version2 : Descending style
 */
void insertSort1(int a[], int n)
{
	if (a == nullptr || n <= 1)
		return;
	/*Descending */
	int i, j, v;
    /* Divide @a into two groups: sorted and unsorted */
    /* sorted group starts with ix 0, unsorted with 1*/
    /* get a ele from unsroted group and insert it into sorted group */
	for (i = 1; i < n; i++)
	{
        /* get a ele from unsorted group */
		v = a[i];
        /* compare @v with the last ele of the sorted group */
        /* interate the sorted group in descending and so on */
		for (j = i - 1; j >= 0; j--)
		{
			if (v > a[j])
			{
                /* "move eles front to back one by one " */
				a[j + 1] = a[j];
			}
			else
			{
				break;
			}
		}
		a[j + 1] = v;
	}
}
/*
 * Implement it in MY style : Ascending
 *
 */
void insertSort2(int a[], int n)
{
    if(a == nullptr || n <= 1)
        return;

    int i, j, v, k;
    /* Ascending */
    for(i = 1; i < n; i++)
    {
        v = a[i];
        /* OK. Interate sorted group in "Ascending style" */
        /* So inner loop is needed */
        for(j = 0; j < i; j++)
        {
            if(v < a[j])
            {
                /* Inner loop */
                for(k = i ; k > j; k--)
                {
                    a[k] = a[k-1];
                }
                break;
            }
        }
        a[j] = v;
    }
}
/* */

static void _insertionSort1(int a[], int n)
{
}

/* from Book: Algorithm  */
static void _insertionSort(int a[], int n)
{
    for(int i = 1; i < n; i++)
    {
        /* Loop from current idx(i) to 0 with j, descending... */
        /* if current ele less than the previous ele, exchange them */
        for(int j = i; j > 0 && _less(a[j], a[j-1]); j--)
        {
            _exch(a, j, j-1);
        }

        //UTIL_ASSERT(_is_range_sorted(a, 0, i));
    }
    //UTIL_ASSERT(_is_array_sorted(a, n));
}
/*
 * from java-ver\Insertion.java
 */
void insertionSort(int a[], int n)
{
    UTIL_ASSERT(a != nullptr);
    UTIL_ASSERT(n >= 1);
    _insertionSort(a, n);
}


